import TreeNode from "./treeNode";
import {Compare, compareType, defaultCompare} from "../utils/Compare";

interface Callback<T> {
    (value: T, ...args: any[]): any;
}

interface BinarySearchTreeInterface<T> {
    compareFn: compareType<T>;
    root: TreeNode<T> | null;

    insert(key: T): void;

    search(key: T): boolean;

    inOrderTraverse(callBack: Callback<T>): void; // 中序遍历
    preOrderTraverse(callBack: Callback<T>): void; // 先序遍历
    postOrderTraverse(callBack: Callback<T>): void; // 后序遍历
    max(): T | undefined; // 返回树中的最大值
    min(): T | undefined; // 返回树中的最小值
    remove(key: T): void;
}

/**
 * 二叉搜索树
 */
export default class BinarySearchTree<T> implements BinarySearchTreeInterface<T> {
    compareFn: compareType<T>;
    root: TreeNode<T> | null;

    constructor(compareFn: compareType<T> = defaultCompare) {
        this.compareFn = compareFn;
        this.root = null;
    }

    // 中序遍历
    // 左节点 父节点 右节点
    inOrderTraverse(callBack: Callback<T>): void {
        this.inOrderTraverseNode(this.root,callBack);
    }

    // 中序遍历辅助函数
    protected inOrderTraverseNode(node:TreeNode<T> | null,callback:Callback<T>): void {
        if(node != null){
            this.inOrderTraverseNode(node.left,callback);
            callback(node.key);
            this.inOrderTraverseNode(node.right,callback)
        }
    }

    insert(key: T): void {
        if (this.root == null) {
            this.root = new TreeNode<T>(key);
        } else {
            this.insertNode(this.root, key);
        }
    }

    protected insertNode(node: TreeNode<T>, key: T): void {
        if(this.compareFn(node.key, key) === Compare.NORMAL_THAN){
            return
        }
        let index:"left" | "right";
        if (this.compareFn(node.key, key) === Compare.LESS_THAN) {
            index = "right";
        } else {
            index = "left";
        }

        if (node[index] == null) {
            node[index] = new TreeNode(key);
        } else {
            this.insertNode(node[index] as TreeNode<T>, key);
        }
    }

    max(): T | undefined{
        if(!this.root){
           return undefined
        }
        return this.maxOrMinNode(this.root,"right").key;
    }

    min(): T | undefined{
        if(!this.root){
           return undefined
        }
        return this.maxOrMinNode(this.root,"left").key;
    }

    // max 和 min的辅助函数
    protected maxOrMinNode(node:TreeNode<T>,key:"right"|"left"):TreeNode<T>{
        // 递归方式实现
        /*
        if(node[key] == null){
            return node.key
        }else{
            return this.maxOrMinNode((node[key] as TreeNode<T>),key);
        }
        */

        // 循环方式实现
        let current = node;
        while (current != null && current[key] != null){
            current = (current[key] as TreeNode<T>);
        }

        return current;
    }

    // 先序遍历
    // 父节点 左节点 右节点
    postOrderTraverse(callBack: Callback<T>): void {
        this.postOrderTraverseNode(this.root,callBack);
    }
    // 先序遍历辅助函数
    protected postOrderTraverseNode(node:TreeNode<T> | null, callback:Callback<T>):void{
        if(node != null){
            callback(node.key);
            this.inOrderTraverseNode(node.left,callback);
            this.inOrderTraverseNode(node.right,callback);
        }
    }

    // 后序遍历
    // 左节点 右节点 父节点
    preOrderTraverse(callBack: Callback<T>): void {
        this.preOrderTraverseNode(this.root,callBack)
    }

    // 后序遍历辅助函数
    protected preOrderTraverseNode(node:TreeNode<T> | null, callback:Callback<T>):void{
        if(node != null){
            this.inOrderTraverseNode(node.left,callback);
            this.inOrderTraverseNode(node.right,callback);
            callback(node.key);
        }
    }

    remove(key: T): void {
        this.root = this.removeNode(this.root, key);
    }
    protected removeNode(node: TreeNode<T> | null, key: T): null|TreeNode<T> {
        if(node == null){
            return null;
        }

        let diffRes = this.compareFn(node.key,key);
        const index = diffRes === Compare.LESS_THAN ?  "right" : "left";
        if(diffRes !== Compare.NORMAL_THAN){
            node[index] = this.removeNode(node[index],key);
            return node
        }else{
            if(!node.left && !node.right){
               return  null
            }else if (node.left && !node.right){
                node = node.left
                return node
            }else if(!node.left && node.right){
                node = node.right
                return node
            }else{
                const minKey = this.maxOrMinNode((node.right as TreeNode<T>),"left").key;
                node.key = minKey;
                node.right = this.removeNode(node.right,minKey);
                return node;
            }

        }

    }

    search(key: T): boolean {
        return this.searchNode(this.root,key)
    }

    protected searchNode(node: TreeNode<T> | null,key:T):boolean{
        if(node == null){
            return false
        }
        const diffRes =  this.compareFn(node.key,key)
        const index=  diffRes === Compare.LESS_THAN ?  "right" : "left";
        if( diffRes === Compare.NORMAL_THAN){
            return true
        }else{
            return this.searchNode(node[index] as TreeNode<T>,key)
        }
    }


}
/*
let tree = new BinarySearchTree<number>();
tree.insert(11);
tree.insert(7);
tree.insert(8);
tree.insert(15);
tree.insert(4);
tree.insert(6);
tree.insert(3);
tree.insert(14);
tree.insert(18);
tree.insert(15);
tree.insert(16);
tree.insert(17);

console.log(tree.min());
console.log(tree.max());
console.log(tree.search(5));
console.log(tree.search(15));
console.log("--------------")
tree.inOrderTraverse(num=>console.log(num))
console.log("--------------")
tree.preOrderTraverse(num=>console.log(num))
console.log("--------------")
tree.postOrderTraverse(num=>console.log(num))
console.log("--------------")
tree.remove(15)
tree.postOrderTraverse(num=>console.log(num))
*/
